import java.util.HashMap;
import java.util.Map;

/**
 * 给定一个整数数组A，返回 A中最长等差子序列的长度。
 * 回想一下，A的子序列是列表A[i_1], A[i_2], ..., A[i_k] 其中0 <= i_1 < i_2 < ... < i_k <= A.length - 1。并且如果B[i+1] - B[i](0 <= i < B.length - 1) 的值都相同，那么序列B是等差的。
 * <p>
 * 示例 1：
 * 输入：[3,6,9,12]
 * 输出：4
 * 解释：
 * 整个数组是公差为 3 的等差数列。
 * <p>
 * 示例 2：
 * 输入：[9,4,7,2,10]
 * 输出：3
 * 解释：
 * 最长的等差子序列是 [4,7,10]。
 * <p>
 * 示例 3：
 * 输入：[20,1,15,3,10,5,8]
 * 输出：4
 * 解释：
 * 最长的等差子序列是 [20,15,10,5]。
 * <p>
 * 提示：
 * 2 <= A.length <= 2000
 * 0 <= A[i] <= 10000
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-arithmetic-subsequence
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Q01027m {
    public int longestArithSeqLength(int[] nums) {
        int ans = 2;
        Map<Integer, Map<Integer, Integer>> map = new HashMap<>();
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                int sub = nums[j] - nums[i];
                Map<Integer, Integer> idxMap = map.get(sub);
                if (idxMap == null) {
                    idxMap = new HashMap<>();
                    map.put(sub, idxMap);
                    idxMap.put(j, 2);
                } else {
                    Integer ic = idxMap.remove(i);
                    if (ic == null) {
                        idxMap.put(j, 2);
                    } else {
                        ++ic;
                        Integer jc = idxMap.remove(j);
                        jc = jc == null ? ic : Math.max(jc, ic);
                        ans = Math.max(ans, jc);
                        idxMap.put(j, jc);
                    }
                }
            }
        }
        return ans;
    }
}
